//动态规划
package algorithm

import (
	"fmt"
	"strconv"
)

func max(i, j int) int {
	if i > j {
		return i
	}
	return j
}

func min(i, j int) int {
	if i < j {
		return i
	}
	return j
}

//0-1背包问题
func ZeroOneBackpack(bpcap int, v []int, w []int) {
	selected := make([][]int, len(v)+1) //选择的物品  selected[i][j]表示容量为j时，前i个物品的最大价值
	selected[0] = make([]int, bpcap+1)
	for i := 1; i <= len(v); i++ {
		selected[i] = make([]int, bpcap+1)
		for j := 1; j <= bpcap; j++ {

			if j-w[i-1] < 0 {
				selected[i][j] = selected[i-1][j]
			} else {
				selected[i][j] = max(selected[i-1][j-w[i-1]]+v[i-1], selected[i-1][j])
			}
		}
	}
	fmt.Println(selected[len(v)][bpcap], selected)
}

//钢条切割问题
//r[i]表示长度为i的最大价值
//p[i]表示长度i的价格
//max(p[i],r[i]+r[n-i])
func CutSteelRod(p []int, n int) {
	res := 0
	r := make([]int, 0)
	//i表示钢条长度
	for i := 0; i <= n; i++ {
		//j表示切割位置
		res = p[i]
		for j := 1; j < i; j++ {
			res = max(res, r[j]+r[i-j])
		}
		r = append(r, res)
	}
	fmt.Println(res, r)
}

//最长公共子序列
//eg s1=ABABBAAAC
//eg s1=BCACBC
//output BABC
// l[i,j]
//i,j=0 0
//i,j>0 xi=yj -> l[i-1,j-1] +1
//i,j>0 xi!=yj max(l[i-1,j]) , l(i,j-1)]
func LCS(s1, s2 string) {
	//最长公共子序列长度
	n := max(len(s1), len(s2)) + 1
	l := make([][]int, n)
	if len(s1) == 0 || len(s2) == 0 {
		l = append(l, []int{0})
	} else if s1 == s2 {
		l = append(l, []int{len(s1)})
	} else {
		//i表示子序列长度
		l[0] = make([]int, n)
		for i := 1; i <= len(s1); i++ {
			l[i] = make([]int, n)
			for j := 1; j <= len(s2); j++ {
				if s1[i-1] == s2[j-1] {
					l[i][j] = l[i-1][j-1] + 1
				} else if s1[i-1] != s2[j-1] {
					l[i][j] = max(l[i-1][j], l[i][j-1])
				}
			}
		}
	}

	fmt.Println(l)
}

//给定一个target值，判断两个数组中是否存在能找到和为target的
//s[i][j]:i表示前i个数，j表示
//若E[
func CanSplitArrayEqual(a []int) {
	sum1 := 0
	for _, v := range a {
		sum1 += v
	}
	//问题转化为能否找到一个子数组和恰为sum/2
	sum := sum1 / 2

	s := make([][]int, len(a)+1)
	s[0] = make([]int, sum+1)
	equal := false
	for i := 1; i <= len(a); i++ {
		s[i] = make([]int, sum+1)
		for j := 1; j <= sum; j++ {
			if j-a[i-1] < 0 {
				s[i][j] = s[i-1][j-1]
			} else {
				s[i][j] = max(s[i-1][j-a[i-1]]+a[i-1], s[i-1][j])
				if s[i][j] == sum && 2*sum == sum1 {
					equal = true
				}
			}
		}
	}
	fmt.Println(equal, s)
}

func LongestPalindrome(s string) string {
	if len(s) == 0 {
		return ""
	}
	var m, n int //分别表示最长回文子串开始和结束下标
	for i := 0; i < len(s); i++ {
		for j := 0; j <= i; j++ {
			if i-j > n-m {
				if s[j] == s[i] && reverseString(s[j:i+1]) {
					m = j
					n = i
					break
				}
			} else {
				break
			}
		}
	}
	return s[m : n+1]
}

func LongestPalindromeDP(s string) string {
	if len(s) == 0 || len(s) == 1 {
		return s
	}
	if len(s) == 2 {
		if s[0] == s[1] {
			return s
		} else {
			return s[0:1]
		}
	}
	f := make([][]bool, len(s))
	var m, n int
	for i := 0; i < len(s); i++ {
		f[i] = make([]bool, len(s))
		f[i][i] = true
	}
	for j := 1; j < len(s); j++ {
		for i := 0; i < j; i++ {
			if s[j] != s[i] {
				f[i][j] = false
			} else {
				if j-i < 3 {
					f[i][j] = true
				} else {
					f[i][j] = f[i+1][j-1]
				}
			}
			if f[i][j] && j-i > n-m {
				m = i
				n = j
			}
		}
	}
	return s[m : n+1]
}

// 反转字符串
func reverseString(s string) bool {
	r := []rune(s)
	for i := 0; i < len(r)/2; i++ {
		if r[i] != r[len(r)-1-i] {
			return false
		}
	}
	return true
}

//. 表示匹配任意单个字符
//* 表示匹配前一个字符的0个或者多个
func StringIsMatchDP(s string, p string) bool {
	begin := 0 //表示上一次特殊字符后面的起点
	c := make([][]string, 0)
	for i := 0; i < len(p); i++ {
		if p[i:i+1] == "." {
			//遇到.*并且.前面无特殊匹配字符时作为一个整体处理
			if i+1 < len(p) && p[i+1:i+2] == "*" {
				if begin<i{
					c = append(c, []string{"",p[begin:i],"-1","-1"})
				}
				c = append(c, []string{"*", ".","-1","-1"})
				begin=i+2
				i++
			} else {
				if begin<i{
					c = append(c, []string{"",p[begin:i],"-1","-1"})
				}
				c = append(c, []string{".", "","-1","-1"})
				begin=i+1
			}

		} else if p[i:i+1] == "*" {
			if begin == i {
				c = append(c, []string{p[i : i+1], "","-1","-1"})
			} else {
				if begin<i-1{
					c = append(c, []string{"",p[begin:i-1],"-1","-1"})
					begin=i-1
				}
				c = append(c, []string{"*", p[begin:i],"-1","-1"})
				begin=i+1
				//若*后面仍然是待匹配的字符，则继续往后面走直到不是或者结束
				if i<len(p)-1&&p[i-1:i]==p[i+1:i+2]{
					t:=i-1
					i++//从*后面的字符开始判断
					for ;i<len(p);i++{
						if p[i:i+1]==p[t:t+1]{
							begin=i+1
						}else {
							if p[i:i+1]=="*"{//表示i-1处的字符是相等的，则外层从i+1开始
								begin=i+1
								continue
							}else if p[i:i+1]=="."{//如果是.则直接跳出，因为外层i还要+1，所以i要先-1
								begin=i
								i=i-1
								break
							}
							//到这里表示是普通字符
							begin=i
							i=i-1
							break
						}
					}
				}
			}
		}
	}
	if len(c) == 0 {
		return s == p
	}

	if begin <= len(p)-1 { //表示还没分割完
		c = append(c, []string{"", p[begin:],"-1","-1"})
	}
	pindex := 0
	ls := len(s)
	start:=-1
	for i := 0; i < ls; i++ {
		if pindex>=len(c){
			return false
		}
		if c[pindex][0] == "." {
			c[pindex][2]=strconv.Itoa(i)
			c[pindex][3]=strconv.Itoa(i)
			pindex++
			continue
		} else if c[pindex][0] == "*" {
			if c[pindex][1] == "." {//.*的情况需要特殊处理
				continue
			} else {
				//如果和当前字符不等，则认为匹配的为0个，pindex直接记录下一个
				if s[i:i+1] != c[pindex][1] {
					if start!=-1{
						c[pindex][2]=strconv.Itoa(start)
						c[pindex][3]=strconv.Itoa(i-1)
					}
					pindex++
					i--
					continue
				}else {
					if start==-1{
						start=i
					}
					if i==ls-1{
						c[pindex][2]=strconv.Itoa(start)
						c[pindex][3]=strconv.Itoa(i)
					}
				}
			}

			if i == ls-1 && pindex < len(c)-1 {
				pindex++
			}
		} else if c[pindex][0] == "" {
			if len(s[i:])<len(c[pindex][1]){
				return false
			}else {
				if c[pindex][1] == s[i:i+len(c[pindex][1])]{
					i=i+len(c[pindex][1])-1
					pindex++
				}else {
					return false
				}
			}
		}
	}
	if pindex>=len(c){
		return true
	}
	return isMatchStringEnd(s,c,pindex)
}

func isMatchStringEnd(s string,c [][]string,pindex int) bool {
	for pindex<len(c){
		if c[pindex][0]=="*"{
			pindex++
		}else if c[pindex][0]==""{
			nindex:=pindex-1
			for nindex>=0{
				if c[nindex][0]=="*"{
					
				}else {
					return false
				}
			}
			return false
		}else if c[pindex][0]=="."{
			if c[pindex-1][0]=="*"{
				pindex++
			}else {
				return false
			}
		}
	}
	return true
}
